"""
https://leetcode.cn/problems/max-area-of-island/description/

695. 岛屿的最大面积
中等
相关标签
相关企业
给你一个大小为 m x n 的二进制矩阵 grid 。

岛屿 是由一些相邻的 1 (代表土地) 构成的组合，这里的「相邻」要求两个 1 必须在 水平或者竖直的四个方向上 相邻。你可以假设 grid 的四个边缘都被 0（代表水）包围着。

岛屿的面积是岛上值为 1 的单元格的数目。

计算并返回 grid 中最大的岛屿面积。如果没有岛屿，则返回面积为 0 。

 

示例 1：


输入：grid = [
[0,0,1,0,0,0,0,1,0,0,0,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,1,1,0,1,0,0,0,0,0,0,0,0],
[0,1,0,0,1,1,0,0,1,0,1,0,0],
[0,1,0,0,1,1,0,0,1,1,1,0,0],
[0,0,0,0,0,0,0,0,0,0,1,0,0],
[0,0,0,0,0,0,0,1,1,1,0,0,0],
[0,0,0,0,0,0,0,1,1,0,0,0,0]
]
输出：6
解释：答案不应该是 11 ，因为岛屿只能包含水平或垂直这四个方向上的 1 。
示例 2：

输入：grid = [[0,0,0,0,0,0,0,0]]
输出：0
 

提示：

m == grid.length
n == grid[i].length
1 <= m, n <= 50
grid[i][j] 为 0 或 1

"""

from typing import List


class Solution:
    """
    仍然采用地图标记走向法
    """
    def maxAreaOfIsland(self, grid: List[List[int]]) -> int:
        height=len(grid)
        width=len(grid[0])
        records=[[0]*width for _ in range(height)]

        def go_next(target:List[int],area:List[int])->bool:
            trow=target[0]
            tcol=target[1]
            if trow<0 or trow>=height or tcol<0 or tcol>=width:
                return False
            if grid[trow][tcol]==0 or records[trow][tcol]==1:
                return False
            records[trow][tcol]=1
            area[0]+=1
            return True
        
        max_area=0
        for r in range(height):
            for c in range(width):
                if grid[r][c]==1 and records[r][c]==0:
                    # 开始遍历一块岛屿的面积
                    records[r][c]=1
                    to_go=[[r,c]]
                    area=[1]
                    while len(to_go)>0:
                        [nr,nc]=to_go[0]
                        # print(to_go)
                        to_go.pop(0)
                        
                        if go_next([nr-1,nc],area):
                            to_go.append([nr-1,nc])
                        if go_next([nr+1,nc],area):
                            to_go.append([nr+1,nc])
                        if go_next([nr,nc-1],area):
                            to_go.append([nr,nc-1])
                        if go_next([nr,nc+1],area):
                            to_go.append([nr,nc+1])
                    max_area=max(area[0],max_area)

        return max_area

if __name__=='__main__':
    grid = [[0,0,0,0,0,0,0,0]]
    sol=Solution()
    res=sol.maxAreaOfIsland(grid)
    print(res)
    pass